package subject_set.offer100;

/**
 * @author haomin
 * @date 2022/10/14 22:37
 **/
public class Offer24 {
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        // 方法一：头插法
        public ListNode reverseList1(ListNode head) {
            if(head == null || head.next == null) return head;
            ListNode dummyHead = new ListNode(-1);
            dummyHead.next = null;
            while(head != null) {
                ListNode next =head.next;
                head.next = dummyHead.next;
                dummyHead.next = head;

                head = next;
            }
            return dummyHead.next;
        }

        // 方法二：双指针
        public ListNode reverseList2(ListNode head) {
            if(head == null || head.next == null) return head;
            ListNode pre = null;
            ListNode cur = head;
            while(cur != null) {
                ListNode next = cur.next;
                cur.next = pre;

                pre = cur;
                cur = next;
            }
            return pre;
        }

        // 方法三：递归
        public ListNode reverseList(ListNode head) {
            if(head == null || head.next == null) return head;
            ListNode second = head.next;
            ListNode newHead = reverseList(head.next);

            second.next = head;
            head.next = null;
            return newHead;
        }
    }
}